เรขาคณิตของความเป็นไปได้
สำหรับปัญหาเว้าที่มีข้อจำกัดเท่ากัน $Ax=b$ เวกเตอร์ $v \in \mathbf{R}^n$ เป็น ทิศทางที่เป็นไปได้ ถ้า $Av = 0$ ซึ่งหมายความว่า การเคลื่อนที่ในทิศทาง $v$ จะคงข้อจำกัดไว้: $A(x+v) = b$ เมื่อ $Ax=b$
เพื่อให้ $x^*$ เป็นจุดที่เหมาะสม อนุพันธ์เชิงทิศทาง $\nabla f(x^*)^T v$ ต้องเป็นศูนย์สำหรับทิศทางที่เป็นไปได้ทุกทิศทาง $v$ ในปริภูมิศูนย์ $\mathcal{N}(A)$ ซึ่งหมายความว่า ค่าอนุพันธ์ $\nabla f(x^*)$ ต้องตั้งฉากกับ $\mathcal{N}(A)$ ส่งผลให้เกิด ตัวคูณลากรองจ์។
จุด $x^*$ เป็นจุดที่เหมาะสมก็ต่อเมื่อมีเวกเตอร์ $\nu^* \in \mathbb{R}^p$ ซึ่งทำให้เกิด
$\nabla f(x^*) + A^T \nu^* = 0$
ซึ่งสร้างระบบสมการเชิงเส้นที่แสดงถึงสมดุลระหว่างการลดลงของฟังก์ชันวัตถุประสงค์และพื้นผิวข้อจำกัด
เกรเดียนต์ที่ฉาย
การ การฉายแบบยูคลิด ของเกรเดียนต์ลบ $-\nabla f(x)$ บนปริภูมิศูนย์ $\mathcal{N}(A)$ กำหนดโดย:
$\Delta x_{\text{pg}} = \text{argmin}_{Au=0} \| -\nabla f(x) - u \|_2$
เวกเตอร์นี้แสดงถึงทิศทางการลดลงที่ดีที่สุดที่เป็นไปได้ โดยสำคัญคือ $x$ เป็นจุดที่เหมาะสมก็ต่อเมื่อ $\Delta x_{\text{pg}} = 0$
ระบบเคเคทีและคุณสมบัติของเมทริกซ์
เราสามารถแก้หาขั้นตอนนิวตันและตัวแปรคู่พร้อมกันโดยใช้ระบบบล็อก:
$$\begin{bmatrix} I & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} v \\ w \end{bmatrix} = \begin{bmatrix} -\nabla f(x) \\ 0 \end{bmatrix}$$หมายเหตุเกี่ยวกับคุณสมบัติสเปกตรัมของเมทริกซ์: เมทริกซ์เคเคทีมีความสมมาตรแต่ ไม่มีทิศทางแน่นอนหากเมทริกซ์ไม่เป็นเอกลักษณ์ จะมีค่าอีเจนที่เป็นบวกจำนวน $n$ และเป็นลบจำนวน $p$ ซึ่งหมายความว่าจุดที่เหมาะสม $(x^*, \nu^*)$ เป็น จุดม้า ของลากรองจียน $L(x, \nu) = f(x) + \nu^T(Ax-b)$ แทนที่จะเป็นจุดต่ำสุดท้องถิ่นอย่างง่ายในพื้นที่ผสมของตัวแปรหลักและคู่